public class QuickSort {
    // 提供简化的公共接口
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 空数组或单元素数组已经有序
        }
        quickSort(arr, 0, arr.length - 1);
    }
    
    // 快速排序主方法
    private static void quickSort(int[] arr, int low, int high) {
        // 对于小规模数组，使用插入排序以提高效率
        if (high - low < 10) {
            insertionSort(arr, low, high);
            return;
        }
        
        if (low < high) {
            // 获取分区点
            int pivotIndex = partition(arr, low, high);
            
            // 递归排序分区点左边的子数组
            quickSort(arr, low, pivotIndex - 1);
            // 递归排序分区点右边的子数组
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    // 分区方法 - 使用三数取中法选择基准值
    private static int partition(int[] arr, int low, int high) {
        // 三数取中法选择基准值
        medianOfThree(arr, low, high);
        
        // 选择最右边的元素作为基准值（已通过三数取中优化）
        int pivot = arr[high];
        
        // i是小于基准值区域的边界
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            // 如果当前元素小于等于基准值，则扩展小于区域
            if (arr[j] <= pivot) {
                i++;
                // 交换arr[i]和arr[j]
                swap(arr, i, j);
            }
        }
        
        // 将基准值放到正确的位置
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    // 三数取中法，优化基准值选择
    private static void medianOfThree(int[] arr, int low, int high) {
        int mid = low + (high - low) / 2;
        
        // 对arr[low], arr[mid], arr[high]进行排序
        if (arr[low] > arr[mid]) {
            swap(arr, low, mid);
        }
        if (arr[low] > arr[high]) {
            swap(arr, low, high);
        }
        if (arr[mid] > arr[high]) {
            swap(arr, mid, high);
        }
        
        // 将中位数放到high-1的位置
        swap(arr, mid, high - 1);
    }
    
    // 插入排序算法，用于小规模数组
    private static void insertionSort(int[] arr, int low, int high) {
        for (int i = low + 1; i <= high; i++) {
            int key = arr[i];
            int j = i - 1;
            
            while (j >= low && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            
            arr[j + 1] = key;
        }
    }
    
    // 交换数组中两个元素的位置
    private static void swap(int[] arr, int i, int j) {
        if (i != j) { // 避免不必要的交换
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    // 打印数组的方法
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    
    // 主方法，用于测试快速排序
    public static void main(String[] args) {
        System.out.println("=== 快速排序实现测试 ===");
        
        // 测试用例1：随机数组
        int[] arr1 = {10, 7, 8, 9, 1, 5};
        System.out.println("排序前的数组1：");
        printArray(arr1);
        sort(arr1); // 使用简化的公共接口
        System.out.println("排序后的数组1：");
        printArray(arr1);
        
        // 测试用例2：已排序数组
        int[] arr2 = {1, 2, 3, 4, 5};
        System.out.println("\n排序前的数组2：");
        printArray(arr2);
        sort(arr2);
        System.out.println("排序后的数组2：");
        printArray(arr2);
        
        // 测试用例3：逆序数组
        int[] arr3 = {5, 4, 3, 2, 1};
        System.out.println("\n排序前的数组3：");
        printArray(arr3);
        sort(arr3);
        System.out.println("排序后的数组3：");
        printArray(arr3);
        
        // 测试用例4：包含重复元素的数组
        int[] arr4 = {3, 1, 4, 1, 5, 9, 2, 6, 5};
        System.out.println("\n排序前的数组4：");
        printArray(arr4);
        sort(arr4);
        System.out.println("排序后的数组4：");
        printArray(arr4);
        
        // 测试用例5：大规模数组
        int[] arr5 = new int[20];
        for (int i = 0; i < arr5.length; i++) {
            arr5[i] = (int) (Math.random() * 100);
        }
        System.out.println("\n排序前的数组5（随机20元素）：");
        printArray(arr5);
        sort(arr5);
        System.out.println("排序后的数组5：");
        printArray(arr5);
    }
}